package com.jiang.专题.动态规划.Q140;

import java.util.ArrayList;
import java.util.List;

/**
 * @author Jiang
 * @version 1.0
 * @date 2025/04/09 13:14
 */
public class Solution {
    private List<String> res = new ArrayList<>();
    private boolean[][] dp;
    private StringBuilder[][] sb;

    // 记忆化搜索
    public List<String> wordBreak(String s, List<String> wordDict) {
        int n = s.length();
        dp = new boolean[n][n];
        sb = new StringBuilder[n][n];

        for (int i = 0; i < n; i++) {
            for (int j = 0; j <= i; j++) {
                if (wordDict.contains(s.substring(j, i + 1))) {
                    dp[j][i] = true;
                    sb[j][i] = new StringBuilder(s.substring(j, i + 1) + " ");
                }
            }
        }
        dfs(0, n, new StringBuilder());
        return res;
    }

    public void dfs(int start, int n, StringBuilder temp) {
        if (start == n) {
            res.add(temp.toString().trim());
            return;
        }

        for (int i = start; i < n; i++) {
            if (dp[start][i]) {
                temp.append(sb[start][i]);
                dfs(i + 1, n, temp);
                temp = temp.delete(temp.length() - sb[start][i].length(), temp.length());
            }

        }
    }

    // 动态规划
//    public List<String> wordBreak(String s, List<String> wordDict) {
//        List<String> res = new ArrayList<>();
//        int len = s.length();
//
//        Set<String> wordSet = new HashSet<>(wordDict);
//
//        boolean[] dp = new boolean[len + 1];
//
//        dp[0] = true;
//
//        for (int i = 1; i <= len; ++i) {
//            for (int j = 0; j < i; ++j) {
//                if (!dp[j]) continue;
//                String sub = s.substring(j, i);
//                if (wordSet.contains(sub)) {
//                    dp[i] = true;
//                    break;
//                }
//            }
//        }
//
//        if (!dp[len]) return res;
//
//        List<String>[] strs = new List[len + 1];
//
//        for (int i = 0; i <= len; ++i) {
//            strs[i] = new ArrayList<>();
//        }
//
//        for (int i = 1; i <= len; ++i) {
//            if (!dp[i]) continue;
//            for (int j = i - 1; j >= 0; --j) {
//                if (!dp[j]) continue;
//                String sub = s.substring(j, i);
//
//                if (!wordSet.contains(sub)) continue;
//
//                if (strs[j].size() == 0) {
//                    strs[i].add(sub);
//                } else {
//                    for (String ss : strs[j]) {
//                        strs[i].add(new StringBuilder(ss).append(" ").append(sub).toString());
//                    }
//                }
//
//            }
//        }
//
//        return strs[len];
//    }
}
